package algorithm.swordoff;

import java.util.HashMap;

/**
 * 最长不含重复字符的子字符串
 * 本题与主站 3 题相同
 *
 * 双指针法,双指针在字符串上移动的过程可以想象滑动窗口,右端逐次+1,左边收缩的过程
 */

public class SQ48 {
    public int lengthOfLongestSubstring(String s) {
        if (s.equals("")) return 0;
        int res = 0;
        int i = -1, j = 0;
        HashMap<Character, Integer> dict = new HashMap<>();

        while (j < s.length()) {
            if (dict.containsKey(s.charAt(j))) {
                i = Math.max(i, dict.get(s.charAt(j)));
            }
            dict.put(s.charAt(j), j);
            res = Math.max(res, j-i);
            j++;
        }
        return res;
    }

    public int dpAndHashMap(String s) {
        if (s.equals("")) return 0;
        int j = 0, res = 0;
        HashMap<Character, Integer> dict = new HashMap<>();

        while (j < s.length()) {
            int i = dict.getOrDefault(s.charAt(j), -1);
            res = j-i <= res ? j-i : res+1;
            dict.put(s.charAt(j), j);
            j++;
        }
        return res;
    }

    public static void main(String[] args) {
        SQ48 sq48 = new SQ48();
        System.out.println(sq48.dpAndHashMap("a"));
    }
}
